This section is intended to introduce the reader to various aspects of the art that may be related to various aspects of the present invention. The following discussion is intended to provide information to facilitate a better understanding of the present invention. Accordingly, it should be understood that statements in the following discussion are to be read in this light, and not as admissions of prior art.
The present invention extends the Blind Stone Tablet paper [1] by Williams et al. That paper introduced a system that supports all of SQL, is distributed, ensures that a putative outsourcing provider TrustMeNot sees only encrypted data, and ensures “access privacy.” Access privacy is the concept that the outsourcing provider TrustMeNot does not know which data clients are accessing regardless of the transaction type. Like that paper, this embodiment guarantees access privacy by essentially the same technique: each client holds a copy of the database so when a client issues a read-only transactions, it does so on local data. When a client issues a read-write transaction (i.e. a transaction that performs at least some insert, delete, or modification) it sends its transaction description in encrypted form to TrustMeNot. So, TrustMeNot records a log of encrypted transaction descriptions, but does not know which data is accessed because all data accesses go to client-local databases. (Periodically, a client may dump an entire database state or download the entire database state for recovery purposes. Such operations preserve access privacy.)
The present invention involves a variant of the algorithm from [1] that guarantees access privacy, deadlock freedom, and wait-freedom. Wait-freedom, a concept introduced by Maurice Herlihy, is the idea that if a client slows down or fails, other clients can still continue making progress. This invention then extends that algorithm to accommodate large data at some loss in access privacy. This invention also extends that algorithm to allow different clients to have access to different data.
Whereas a direct predecessor of the present invention is the Blind Stone Tablet paper, this work has been heavily influenced by other research. The paper on k-anonymity by Samarati and Sweeney [2] introduced an entire approach to understanding the implications that aggregate queries could have on the privacy of individuals. Whereas others have chosen to establish positive results based on this idea, e.g. by making k large, the present invention preferred to follow the Blind Stone Tablet absolutist approach of full access privacy. As this approach to blobs requires some compromise, it was foreseen in future developments that make use of these fundamental concepts, as is done for example in [3] which stores some information on the client and some on the server.
In addition, the algorithms for searching encrypted data for XML query processing [4], range queries [5,6], and aggregates [7] shows that much can be done on such data if accesses are limited to queries. As for work that tries to handle large portions of SQL in the spirit of Hacigumus et al. [8], the idea of mixing public and private data with some guarantee of something close to k-anonymity is desired.
Finally, there is work concerned with guaranteeing the integrity of databases [9,11], audit logs [10], and data structures [12] that inspires the method Blind Stone Tablet (and we) use to establish fork consistency.